#include <string>
#include <utility>
#include <cctype>
#include <algorithm>
#include <sstream>

#include "big_int.h"
#include "optimized_vector.h"

namespace 
{
   int str_to_num(std::string s)
   {
      std::istringstream stream(s);
      int res;
      stream >> res;
      return res;
   }

   std::string num_to_str(int i) 
   {
      std::ostringstream stream;
      stream << i;
      return stream.str();
   }   
}

big_int::big_int(long long number): is_negative_(number < 0)
{
   if (number < 0)
   {
      number = -number;
   }
   while (number != 0)
   {
      digits_.push_back(number % BASE);
      number /= BASE;
   }
}

big_int::big_int(std::string s)
{
   if (s[0] == '-')
   {
      is_negative_ = true;
      s = s.substr(1, s.length() - 1);
   }
   else
   {
      is_negative_ = false;
      if (s[0] == '+')
      {
         s = s.substr(1, s.length() - 1);
      }
   }
   while (s.length() >= BASE_LENGTH)
   {
      digits_.push_back(str_to_num(s.substr(s.length() - BASE_LENGTH, BASE_LENGTH)));
      s = s.substr(0, s.length() - BASE_LENGTH);
   }
   if (s.length() > 0)
   {
      digits_.push_back(str_to_num(s));
   }
   cut_leading_zeroes();
}

big_int& big_int::operator +=(const big_int& number)
{
   big_int number_abs = abs(static_cast<big_int>(number));
   if ((*this).is_negative_)
   {
      big_int value = abs(static_cast<big_int>(*this));
      if (number.is_negative_)
      {
         *this = -(value + number_abs);
      } 
      else
      {
         *this = -(value - number_abs);
      }
      return *this;
   }
   if (number.is_negative_)
   {
      *this -= number_abs;
      return *this;
   }
   size_t max_size = std::max(number.get_size(), get_size());
   big_int a(number); 
   a.add_leading_zeroes(max_size);
   add_leading_zeroes(max_size);
   int transfer = 0; 
   for (size_t i = 0; i < max_size; i++)
   {
      int sum = digits_[i] + a.digits_[i] + transfer;
      digits_[i] = sum % BASE;
      transfer = sum / BASE;
   }
   if (transfer > 0) 
   {
      digits_.push_back(transfer);
   }
   a.cut_leading_zeroes();
   cut_leading_zeroes();
   return *this;         
}

big_int& big_int::operator -=(const big_int& number)
{
   big_int number_abs = abs(static_cast<big_int>(number));
   big_int value = abs(static_cast<big_int>(*this));
   if (value < number_abs)
   {
      *this = -(number - *this);
      return *this;
   }
   if ((*this).is_negative_)
   {
      big_int value = abs(static_cast<big_int>(*this));
      if (number.is_negative_)
      {
         *this = -(value - number_abs);
         return *this;
      } 
      else
      {
         *this = -(value + number_abs);
         return *this;
      }
   }
   if (number.is_negative_)
   {
      *this += number_abs;
      return *this;
   }
   size_t max_size = std::max(number.get_size(), get_size());
   big_int a(number); 
   a.add_leading_zeroes(max_size);
   add_leading_zeroes(max_size);
   int transfer = 0; 
   for (size_t i = 0; i < max_size; i++)
   {
      int sum = digits_[i] - a.digits_[i] + transfer;
      if (sum < 0)
      {
         digits_[i] = (BASE + sum) % BASE;
         transfer = -1;
      } else 
      {
         digits_[i] = sum % BASE;
         transfer = 0;
      }
   }
   a.cut_leading_zeroes();
   cut_leading_zeroes();
   return *this;         
}

big_int& big_int::operator <<=(size_t shift)
{
   size_t old_size = get_size();
   digits_.resize(old_size + shift);
   for (int i = int(old_size + shift) - 1; i >= (int) shift; i--)
   {
      digits_[i] = digits_[i - shift];
   }
   for (size_t i = 0; i < shift; i++)
   {
      digits_[i] = 0;
   }
   return *this;
}

big_int& big_int::operator >>=(size_t shift)
{
   size_t old_size = get_size();
   for (size_t i = shift; i < old_size; i++)
   {
      digits_[i - shift] = digits_[i];
   }
   for (size_t i = old_size - shift; i < old_size; i++)
   {
      digits_.pop_back();
   }
   return *this;
}

big_int& big_int::operator *=(const big_int& a)
{
   big_int res;
   big_int value  = abs(static_cast<big_int>(*this));
   for (size_t i = 0; i < a.get_size(); i++)
   {
      big_int cur = (value * a.digits_[i]) << i;
      res += cur;
   }
   res.is_negative_ = is_negative_ ^ a.is_negative_;
   *this = res;
   return *this;
}

big_int& big_int::operator *=(int a)
{ 
   if (a >= BASE || a < 0)
   {
      return *this *= big_int(a);
   }

   int transfer = 0; 
   for (size_t i = 0, j = get_size(); i < j; i++)
   {
      long long mul = (long long)digits_[i] * a + transfer;
      digits_[i] = mul % BASE;
      transfer = int(mul / BASE);
   }
   if (transfer > 0) 
   {
      digits_.push_back(transfer);
   }
   cut_leading_zeroes();
   return *this;
}

std::pair<big_int, big_int> big_int::divide_with_remainer(const big_int& divider) const
{
   size_t shift;
   if (int(get_size()) - int(divider.get_size()) >= 0)
   {
      shift = get_size() - divider.get_size();
   }
   else
   {
      shift = 0;
   }
   big_int a = abs(static_cast<big_int>(*this));
   big_int b = abs(divider << shift);
   big_int ans;
   for (size_t i = 0; i <= shift; i++)
   {
      int mul = big_int::binary_search(a, b);
      ans.digits_.push_back(mul);
      a -= b * mul;
      b >>= 1;
   }
   ans.digits_.reverse();
   //std::reverse(ans.digits_.begin(), ans.digits_.end());
   ans.cut_leading_zeroes();
   ans.is_negative_ = is_negative_ ^ divider.is_negative_;
   a.is_negative_ = is_negative_;
   return std::make_pair(ans, a);
}

bool big_int::operator ==( const big_int& a) const
{
   return compare_to(a) == 0;
}

bool big_int::operator !=( const big_int& a) const
{
   return compare_to(a) != 0;
}

bool big_int::operator >=( const big_int& a) const
{
   return compare_to(a) >= 0;
}

bool big_int::operator >( const big_int& a) const
{
   return compare_to(a) > 0;
}

bool big_int::operator <=( const big_int& a) const
{
   return compare_to(a) <= 0;
}

bool big_int::operator <( const big_int& a) const
{
   return compare_to(a) < 0;
}

std::istream& operator >>(std::istream& stream, big_int& num)
{
   while (isspace(stream.peek()))
   {
      stream.get();
   }
   if (stream.eof())
   {
      stream.setstate(std::ios::failbit);
      return stream;
   }
   bool negative = false;
   if (stream.peek() == '+' || stream.peek() == '-')
   {
      negative = (stream.peek() == '-');
      stream.get();
   }
   if (!isdigit(stream.peek()))
   {
      stream.setstate(std::ios::failbit);
      return stream;
   }
   std::string buffer;
   while (isdigit(stream.peek()))
   {
      buffer += static_cast<char>(stream.get());
   }
   num = big_int(buffer);
   if (negative)
   {
      num = -num;
   }
   return stream;
}

std::ostream& operator <<(std::ostream& stream, const big_int& number)
{
   if (number.get_size() == 0)
   {
      return stream << 0;
   }
   if (number.is_negative_)
   {
      stream << '-';
   }
   stream << num_to_str(number.digits_.back());
   for (int i = number.get_size() - 2; i >= 0; i--)
   {
      std::string s = num_to_str(number.digits_[i]);
      stream << std::string(number.BASE_LENGTH - s.size(), '0') << s;
   }
   return stream;
}

int big_int::binary_search(big_int border, big_int number)
{
   int l = 0;
   int r = BASE;
   while (l != r - 1)
   {
      int m = (l + r) / 2;
      if (number * m <= border )
      {
         l = m; 
      } else
      {
         r = m;
      }
   }
   return l;
}

size_t big_int::get_size() const
{
   return digits_.size();
}

void big_int::add_leading_zeroes(size_t new_size) 
{
   if (new_size <= get_size()) 
   {
      return;
   }
   for (size_t i = 0, j = new_size - get_size(); i < j; i++)
   {
      digits_.push_back(0);
   }
}

void big_int::cut_leading_zeroes()
{
   while (digits_.size() > 0 && digits_.back() == 0)
   {
      digits_.pop_back();
   }
}

int big_int::compare_to(const big_int& a) const
{
   if (get_size() == a.get_size() && get_size() == 0)
   {
      return 0;
   }
   if (is_negative_ && !a.is_negative_)
   {
      return -1;
   }
   if (!is_negative_ && a.is_negative_)
   {
      return 1;
   }
   int minus = is_negative_ ? -1 : 1;
   if (get_size() != a.get_size())
   {
      return minus * (get_size() - a.get_size());
   }
   for (int i = get_size() - 1; i >= 0; i--)
   {
      if (digits_[i] != a.digits_[i])
      {
         return minus * (digits_[i] - a.digits_[i]); 
      }
   }
   return 0;
}

big_int big_int::operator-() const
{
   big_int a(*this);
   a.is_negative_ = !a.is_negative_;
   return a;
}


big_int operator +(const big_int& a, const big_int& b)
{
   big_int c(a);
   c += b;
   return c;
}

big_int operator -(const big_int& a, const big_int& b)
{
   big_int c(a);
   c -= b;
   return c;
}


big_int operator *(const big_int& a, int b)
{ 
   big_int c(a);
   c *= b;
   return c;
}

big_int operator *(const big_int& a, const big_int& b)
{ 
   big_int c(a);
   c *= b;
   return c;
}

big_int operator <<(const big_int& a, int b)
{ 
   big_int c(a);
   c <<= b;
   return c;
}

big_int operator >>(const big_int& a, int b)
{ 
   big_int c(a);
   c >>= b;
   return c;
}

big_int operator/( const big_int& a, const big_int& b )
{
   big_int c(a);
   c /= b;
   return c;
}

big_int operator%( const big_int& a, const big_int& b )
{
   big_int c(a);
   c %= b;
   return c;
}

big_int abs( big_int& a)
{
   if (a.is_negative())
   {
      return -a;
   } 
   else
   {
      return a;
   }
}

big_int& big_int::operator /=(const big_int&a)
{
   *this = divide_with_remainer(a).first;
   return *this;
}

big_int& big_int::operator %=(const big_int&a)
{
   *this = divide_with_remainer(a).second;
   return *this;
}

bool big_int::is_negative() const
{
   return is_negative_;
}

void big_int::swap(big_int& a)
{
   digits_.swap(a.digits_);
   std::swap(is_negative_, a.is_negative_);
}
